import java.util.Arrays;

/**
 * Creater with IntelliJ IDEA.
 * Description:堆的复习
 * User: 86152
 * Dae: 2022-07-06
 * Time: 14:25
 */
public class Heap {
    public int[] elem;
    public int usedSize;
    public Heap() {
        this.elem=new int[10];
    }
    public void createHeap(int[] array) {
        for(int i=0;i< array.length;i++) {
            elem[i]=array[i];
        }
        for(int p=(usedSize-1-1)/2;p>=0;p--) {
            shiftDown(p,usedSize);
        }
    }

    public void shiftDown(int root,int len) {
        int parent=root;
        int child=root*2+1;
        while(child>len) {
            if(child+1<len && elem[child]<elem[child+1]) {
                child++;
            }
            if(elem[child]>elem[parent]) {
                int tem=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tem;
                parent=child;
                child=parent*2+1;
            } else {
                break;
            }
        }
    }

    public void push(int val) {
        if(usedSize==elem.length) {
            Arrays.copyOf(elem, elem.length+1);
        }
        elem[usedSize]=val;
        shiftUp(usedSize);
        usedSize++;
    }

    public void shiftUp(int child) {
        int parent=(child-1)/2;
        while(child>0) {
            if(elem[child]>elem[parent]) {
                int tem=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tem;
                child=parent;
                parent=(child-1)/2;
            } else {
                break;
            }
        }
    }

    public void pop() {
        if(usedSize==0) {
            System.out.println("优先队列为空");
            return;
        }
        int tem=elem[0];
        elem[0]=elem[usedSize-1];
        elem[usedSize-1]=tem;
        usedSize--;
        shiftDown(0,usedSize);

    }

}
